import java.util.Arrays;

//最长递增子数组的长度
public class LongestIncreasingInnerArr {
}
class LongestIncreasingInnerArrSolution {
    public int lengthOfLIS(int[] nums) {
        int count = 1;
        int n = nums.length;
        int[] res = new int[]{nums[0]};
        for(int i=1;i<n;i++){
            if(nums[i]>res[res.length-1]){
                res = Arrays.copyOf(res,res.length+1);
                res[res.length-1] = nums[i];
            }else if(nums[i]<res[res.length-1]){
                int index = helfSearch(res,nums[i]);
                res[index] = nums[i];
            }
        }
        return res.length;
    }
    int helfSearch(int[] nums,int target){
        int l = 0;
        int r = nums.length-1;
        while(l<=r){
            int m = (l+r)/2;
            if(nums[m]==target)return m;
            else if(nums[m]>target)r = m-1;
            else l = m+1;
        }
        return l;
    }
}